#include <stdio.h>
#include<math.h>
#include <stdint.h>
#include "aim.h"
#include <stdlib.h>


typedef uint32_t uint_t;
typedef unsigned char byte_t;
static const uint_t uint_t_BITS_SIZE = 32;

// values of (sin(y * M_PI*2 / 64) * 16 + 16); for y in [0, 64)
static const uint_t sinTable [] = { 15, 17, 19, 20, 22, 23, 24, 26,
                                  27, 28, 29, 30, 30, 31, 31, 31,
                                  32, 31, 31, 31, 30, 30, 29, 28,
                                  27, 26, 24, 23, 22, 20, 19, 17,
                                  16, 14, 12, 11,  9,  8,  7,  5,
                                   4,  3,  2,  1,  1,  0,  0,  0,
                                   0,  0,  0,  0,  1,  1,  2,  3,
                                   4,  5,  7,  8,  9, 11, 12, 14};

static const byte_t BitReverseTable256[] =
{
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};
//static const byte_t reversed[256];

static inline uint_t reverseSubBytes(uint_t t){

    uint_t result = BitReverseTable256[(t & 0xFF000000) >> 24];
    result = (result << 8) | BitReverseTable256[(t & 0xFF0000) >> 16];
    result = (result << 8) | BitReverseTable256[(t & 0xFF00) >> 8];
    result = (result << 8) | BitReverseTable256[(t & 0xFF)];
    return result;
}


static inline uint_t reverseSubBytes2(uint_t t){

    uint_t result = (t & 0xFF);
    result = (result << 8) | ((t & 0xFF00) >> 8);
    result = (result << 8) | ((t & 0xFF0000) >> 16);
    result = (result << 8) | ((t & 0xFF000000) >> 24);
    return result;
}


static inline uint_t getMovement(uint_t y){
    //equal results for y < 10000000
    uint_t r = y % 64;
    if ( r == 0 ){
        return (uint_t) (sin(y * M_PI*2 / 64) * 16 + 16);
    }else if (r == 32){
         return (uint_t) (sin(y * M_PI*2 / 64) * 16 + 16);
    }else{
        return sinTable[r];
    }
}



//const uint_t startTable [] = {0, ~0};


void show(struct image * restrict out){
	for(int y = 0; y < out->rows; ++y){
		uint_t mov = getMovement(y);
		if (mov == 32){
		//	putchar('-'); putchar('\n');
		}
		for(int x = 0; x < out->cols; ++x){
			bool p = image_getpixel(out, x, y);
			putchar(".#"[p]);
		}
		putchar('\n');
	}
	putchar('\n');
}

void
exercise0(struct image * restrict in, struct image * restrict out);

static struct image * copy(struct image * in){
	int cols = in->cols;
	int rows = in->rows;
	uint_t innerLoopSteps = cols / uint_t_BITS_SIZE;
        struct image *img = malloc(sizeof(*img));

	uint_t * pout;
	uint_t * pin;

	img->cols = cols, img->rows = rows;
	img->bitmap = malloc(img->rows * image_rowbytes(img));
	
	pout = (uint_t *) img->bitmap;
	pin = (uint_t *)  in->bitmap;


	for( int y = 0; y < rows; ++y ){
		for( uint_t * end = pin + innerLoopSteps; pin != end; ++pin, ++pout){
			*pout = *pin;
		}
	}

	return img;
}


void check(struct image * restrict in, struct image * restrict out){
	struct image * restrict outCopy = copy( out );
	int steps = out->rows * ( out->cols / uint_t_BITS_SIZE);
	bool ok = true;
	uint_t * img1,* img2,* end;
	exercise0(in, out);
	img1 = (uint_t *) out->bitmap;
	img2 = (uint_t *) outCopy->bitmap;
	end = img1 + steps;


	
	for(; img1 != end; ++img1, ++img2 ){
		if ( *img1 != *img2 ){
			ok = false;
			break;
			putchar('n');
			putchar('\n');
		}
	}
	if ( ! ok ){
		char arr [] = "not ok\n";
		for( int i = 0; i < sizeof(arr) / sizeof(char); ++i) {
			putchar(arr[i]);
		}
	}else{
		char arr[] = "ok\n";
		for( int i = 0; i < sizeof(arr)/sizeof(char); ++i){
			putchar(arr[i]);
		}
	}
//	putchar('\n');
//	show( out );
//	putchar('\n');
//	show( outCopy );
//	putchar('\n');

}


void
exercise(struct image * restrict in, struct image * restrict out){
	/* Do your image transformation here. Delete the code below
	 * first, especially when testing with large images! Modify
	 * the image, not just the printing code. */

    uint_t * pin =(uint_t *) in->bitmap;
    uint_t * pout = (uint_t *) out->bitmap;

    const uint_t startTable [] = {0, ~0};

    uint_t innerLoopSteps = in->cols / uint_t_BITS_SIZE;

    for (uint_t y = 0; y < in->rows; y++) {

        uint_t movement = getMovement(y);

	if ( movement == 0 ){
		 for(uint_t * end = pin + innerLoopSteps; pin != end; ++pin, ++pout){
		 	*pout = *pin;
		 }
	}else if (movement == 32 ){
		//bool p = image_getpixel( in, 0, y );
 		 bool p = ((*pin) >> 7) & 1;
		 uint_t previous = startTable[p];
		 for(uint_t * end = pin + innerLoopSteps; pin != end; ++pin, ++pout){
 		       *pout = previous;
        	       previous = *pin;
		 }
	}else{

		// (img->bitmap[image_rowbytes(img) * y + x / 8] >> (7 - x % 8)) & 1;
		//bool p = image_getpixel( in, 0, y );
		bool p = ((*pin) >> 7) & 1;
		uint_t previous = startTable[p];
		uint_t current;
		uint_t leftShift = uint_t_BITS_SIZE - movement;
 	        for(uint_t * end = pin + innerLoopSteps; pin != end; ++pin, ++pout){
        	    current = reverseSubBytes2(*pin);
	            *pout =  reverseSubBytes2( (previous << leftShift) | (current >> movement) );
	            previous = current;
		}
	}
    }
//    check( in, out );       
}



void
exercise0(struct image * restrict in, struct image * restrict out)
{
//    char firstCol[ in->rows ];
    /* Do your image transformation here. Delete the code below
     * first, especially when testing with large images! Modify
     * the image, not just the printing code. */
    for (int y = 0; y < in->rows; y++) {
        int movement = getMovement(y);
        bool p = image_getpixel(in, 0, y);
        for (int x = 0; x < in->cols; x++) {
            if ( x - movement >= 0){
                p = image_getpixel(in, x-movement, y);
            //    image_putpixel(out, x, y, p);
            }
            image_putpixel(out, x, y, p);
        }
    }
}
